131. Palindrome Partitioning.c

/*
131. Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.


Return all possible palindrome partitioning of s.


For example, given s = "aab",

Return
[
 ["aa","b"],
 ["a","a","b"]
]
*/

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
typedefstruct {
intstart;
intlen;
} buff_t;
typedefstruct {
char***p;
int*csz;
intpsz;
intpn;
} res_t;
voidadd2res(res_t*res, constchar*s, buff_t*buff, intd) {
inti;
char*str, **pp;
if (res->psz==res->pn) {
res->psz= (res->psz==0) ? 10 : res->psz*2;
res->p=realloc(res->p, res->psz*sizeof(char**));
res->csz=realloc(res->csz, res->psz*sizeof(int));
//assert(res->p && res->psz);
 }
pp=malloc(d*sizeof(char*));
//assert(pp);
for (i=0; i<d; i++) {
str=strndup(&s[buff[i].start], buff[i].len);
pp[i] =str;
 }
res->p[res->pn] =pp;
res->csz[res->pn++] =d;
}
intis_palindrome(constchar*s, intstart, intend) {
while (start<end) {
if (s[start] !=s[end]) return0;
start++;
end--;
 }
return1;
}
voidbt(constchar*s, intstart, intsz, buff_t*buff, intd, res_t*res) {
inti;
if (start==sz) {
// done, save result
add2res(res, s, buff, d);
return;
 }
for (i=start; i<sz; i++) {
if (is_palindrome(s, start, i)) {
buff[d].start=start;
buff[d].len=i-start+1;
bt(s, i+1, sz, buff, d+1, res);
 }
 }
}
char***partition(char*s, int**columnSizes, int*returnSize) {
res_tres= { 0 };
buff_t*buff;
intsz;

sz=strlen(s);

buff=malloc(sz*sizeof(buff_t));
//assert(buff);

bt(s, 0, sz, buff, 0, &res);

//free(buff);

*columnSizes=res.csz;
*returnSize=res.pn;

returnres.p;
}


/*
Difficulty:Medium
Total Accepted:104.5K
Total Submissions:308.3K


Companies Bloomberg
Related Topics Backtracking
Similar Questions 


 Palindrome Partitioning II
*/